#pragma once
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <time.h>
#include <stack>

void InsertSort(std::vector<int> &num)
{
    int n = num.size();
    for (int i = 1; i < n; i++)
    {
        int tmp = num[i], end = i - 1;
        while (end >= 0 && num[end] > tmp)
        {
            num[end + 1] = num[end];
            end--;
        }
        num[end + 1] = tmp;
    }
}

// 快排小区间优化
void InsertSortToQuick(std::vector<int> &num, int l, int r)
{
    for (int i = l + 1; i <= r; i++)
    {
        int tmp = num[i], end = i - 1;
        while (end >= 0 && num[end] > tmp)
        {
            num[end + 1] = num[end];
            end--;
        }
        num[end + 1] = tmp;
    }
}

void Print(const std::vector<int> &num)
{
    for (auto &x : num)
    {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

bool check(const std::vector<int> &nums)
{
    for (size_t i = 1; i < nums.size(); i++)
    {
        if (nums[i] < nums[i - 1])
            return false;
    }
    return true;
}

void ShellSort(std::vector<int> &nums)
{
    int n = nums.size();
    int gap = n - 1;
    while (gap > 1)
    {

        gap = gap / 3 + 1;
        for (int i = 0; i < n - gap; i++)
        {
            int end = i;
            int tmp = nums[end + gap];
            while (end >= 0)
            {
                if (nums[end] > tmp)
                {
                    std::swap(nums[end], nums[end + gap]);
                    end -= gap;
                }
                else
                    break;
            }
            nums[end + gap] = tmp;
        }
    }
}

void IsTrue(const std::vector<int> &num)
{
    std::cout << std::endl;
    if (check(num))
        std::cout << "Yes!!" << std::endl;
    else
        std::cout << "No!!" << std::endl;
}

int ThreeMid(const std::vector<int> &nums, int l, int r)
{
    //[2,1]
    int mid = l + (r - l) / 2;
    if (nums[l] < nums[r]) // l < r
    {
        if (nums[l] > nums[mid])
            return l;
        else if (nums[r] > nums[mid])
            return mid; // l < m < r
        else
            return r;
        // l <r<mid
    }
    else // l > r
    {
        if (nums[l] < nums[mid])
            return mid; // mid > l > r
        else if (nums[r] > nums[mid])
            return r; // l > r   > mid
        else
            return mid; // l > mid > r
    }
    return -1;
}

// 挖坑法
int PartSort1(std::vector<int> &nums, int l, int r)
{
    if (l >= r)
        return l;
    // std::cout << " l " << nums[l] << " m " << nums[l + (r-l) / 2] << " r " << nums[r] << " ";
    int midIndex = ThreeMid(nums, l, r);
    // std::cout << " Mid " << nums[midIndex] << std::endl;
    std::swap(nums[l], nums[midIndex]);
    int pivot = l;
    int start = l, end = r, tmp = nums[pivot];
    while (start < end)
    {
        // 找小于tmp的数字, 不能两边都包含等于tmp，不然会死循环 ,不断地 == tmp等 ,end和start两个位置卡死
        while (end > start && nums[end] >= tmp)
        {
            end--;
        }
        // 此时end指向 < tmp的数字
        nums[pivot] = nums[end];
        pivot = end;
        // 找>=tmp的数字
        while (end > start && nums[start] < tmp)
        {
            start++;
        }
        nums[pivot] = nums[start];
        pivot = start;
    }
    pivot = start;
    nums[pivot] = tmp;
    return pivot;
}

// 霍尔法 (左右指针)
int PartSort2(std::vector<int> &nums, int l, int r)
{
    if (l >= r)
        return l;
    int midIndex = ThreeMid(nums, l, r);
    std::swap(nums[l], nums[midIndex]);
    int keyi = l;
    int start = l, end = r;
    while (start < end)
    {
        // 找小于tmp的数字
        while (end > start && nums[end] >= nums[keyi])
        {
            end--;
        }
        // 此时end指向 < tmp的数字
        /////////////////////////////////////////
        // 找>=tmp的数字
        while (end > start && nums[start] < nums[keyi])
        {
            start++;
        }
        std::swap(nums[start], nums[end]);
    }
    std::swap(nums[start], nums[keyi]);
    return start;
}

// 前后指针法
int PartSort3(std::vector<int> &nums, int l, int r)
{
    int midIndex = ThreeMid(nums, l, r);
    std::swap(nums[l], nums[midIndex]);
    int keyi = l;
    int pre = l, cur = l + 1;
    while (cur <= r) // 闭区间
    {
        if (nums[cur] <= nums[keyi])
        {
            pre++;
            std::swap(nums[pre], nums[cur]);
        }
        cur++;
    }
    std::swap(nums[pre], nums[keyi]);
    return pre;
}

void QuickSort(std::vector<int> &nums, int l, int r)
{
    if (l >= r)
        return;
    int mid = PartSort1(nums, l, r);
    // int mid = PartSort2(nums, l, r);
    //  int mid = PartSort3(nums, l, r);
    if (mid - l < 14)
        InsertSortToQuick(nums, l, mid - 1);
    else
        QuickSort(nums, l, mid - 1);
    if (r - mid < 14)
        InsertSortToQuick(nums, mid + 1, r);
    else
        QuickSort(nums, mid + 1, r);
}

void QuickSortNoR(std::vector<int> &nums, int l, int r)
{
    std::stack<int> pos;
    pos.push(r);
    pos.push(l);
    while (pos.size() > 1)
    {
        int left = pos.top();
        pos.pop();
        int right = pos.top();
        pos.pop();
        if (right - left + 1 < 14)
        {
            InsertSortToQuick(nums, left, right);
            continue;
        }
        int mid = PartSort1(nums, left, right);
        if (right > mid + 1)
        {
            pos.push(right);
            pos.push(mid + 1);
        }
        if (left < mid - 1)
        {
            pos.push(mid - 1);
            pos.push(left);
        }
    }
}
void MergeSort(std::vector<int> &nums, int l, int r, std::vector<int> &tmp)
{
    if (l >= r)
        return;
    int mid = l + (r - l) / 2;
    MergeSort(nums, l, mid, tmp);
    MergeSort(nums, mid + 1, r, tmp);

    int begin1 = l, end1 = mid, begin2 = mid + 1, end2 = r, begin3 = l;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (nums[begin1] < nums[begin2])
            tmp[begin3++] = nums[begin1++];
        else
            tmp[begin3++] = nums[begin2++];
    }
    while (begin1 <= end1)
        tmp[begin3++] = nums[begin1++];
    while (begin2 <= end2)
        tmp[begin3++] = nums[begin2++];
    for (int i = l; i <= r; i++)
    {
        nums[i] = tmp[i];
    }
}

void MergeSortNoR(std::vector<int> &nums, std::vector<int> &tmp)
{
    int gap = 1, n = nums.size();
    while (gap < n)
    {
        for (int i = 0; i < n - gap; i += (2*gap))
        {
            int begin1 = i, end1 = i+gap-1, begin2 = i+gap, end2 = i+2*gap-1, begin3 = i;
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (nums[begin1] < nums[begin2])
                    tmp[begin3++] = nums[begin1++];
                else
                    tmp[begin3++] = nums[begin2++];
            }
            while (begin1 <= end1)
                tmp[begin3++] = nums[begin1++];
            while (begin2 <= end2)
                tmp[begin3++] = nums[begin2++];
            // for (int j = i; j < begin3; j++)
            // {
            //     nums[j] = tmp[j];
            // }
        }
        for (int j = 0; j < n; j++)
        {
            nums[j] = tmp[j];
        }
        gap *= 2;
    }
}

// class Sort
// {
// public:

// private:

// };
